#include "common.h"

int findTargetSumWays(int* nums, int numsSize, int target);

int main()
{
	int nums[] = { 1000 };
	int numsSize = 1;
	int target = -1000;
	findTargetSumWays(nums, numsSize, target);
	return 0;
}

int findTargetSumWays(int* nums, int numsSize, int target)
{
	int sum = 0;
	for (int i = 0; i < numsSize; i++)
		sum += nums[i];
	if (target > sum || sum - target & 1 != 0)
		return 0;

	unsigned int neg_sum = sum - target >> 1;
	unsigned int f[numsSize + 1][neg_sum + 1];
	memset(f, 0, sizeof(f));
	f[0][0] = 1;
	for (int i = 1; i <= numsSize; i++) {
		int cur_num = nums[i - 1];
		for (int j = 0; j <= neg_sum; j++) {
			f[i][j] += f[i - 1][j];
			if (j >= cur_num)
				f[i][j] += f[i - 1][j - cur_num];
		}
	}

	return f[numsSize][neg_sum];
}
